package io.zouyalong.algo.leetcode;

/**
 * https://leetcode-cn.com/problems/house-robber-ii/
 *
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 *
 * 示例 1:
 *
 * 输入: [2,3,2]
 * 输出: 3
 * 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class HouseRobber2 {
    public static void main(String[] args) {
        var input = new int[]{2,3,2,1};
        System.out.printf("Out: %d", HouseRobber2.dp(input));
    }
    public static int dp(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        var n = nums.length;
        return Math.max(sub(nums, 0, n-2), sub(nums, 1, n-1));
    }

    public static int sub(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int n_2 = nums[left];
        int n_1 = Math.max(nums[left+1], n_2);
        for (int i = left+2; i <= right; i++) {
            int rob = nums[i] + n_2;
            int notRob = n_1;
            n_2 = n_1;
            n_1 = Math.max(rob, notRob);
        }
        return n_1;
    }
}
